#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>


#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>

#include "hash_table.h"

using std::string;
static const int kNumFacets = 54;
static const int kNumMoves = 18;

static const size_t k0 = 1;
static const size_t k1 = 18;
static const size_t k2 = 243;
static const size_t k3 = 3240;
static const size_t k4 = 43239;
static const size_t k5 = 574908;
static const size_t k6 = 7618438;
static const size_t k7 = 100803036;
static const size_t k8 = 1332343288;

static const size_t kNumPos[] = { k0, k1, k2, k3, k4, k5, k6, k7, k8 };
// 17596479795,        // 9
// 232248063316,       // 10
// 3063288809012,      // 11
// 40374425656248,     // 12
// 531653418284628,    // 13
// 6989320578825358,   // 14
// 91365146187124313,  // 15

typedef uint8_t Permutation[kNumFacets];

static const Permutation p_0 = {
  0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
  9 , 10, 11, 12, 13, 14, 15, 16, 17,
  18, 19, 20, 21, 22, 23, 24, 25, 26,
  27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 37, 38, 39, 40, 41, 42, 43, 44,
  45, 46, 47, 48, 49, 50, 51, 52, 53,
};

static const Permutation p_R1 = {
  0 , 1 , 47, 3 , 4 , 50, 6 , 7 , 53,
  15, 12, 9 , 16, 13, 10, 17, 14, 11,
  44, 19, 20, 41, 22, 23, 38, 25, 26,
  27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 37, 2 , 39, 40, 5 , 42, 43, 8 ,
  45, 46, 24, 48, 49, 21, 51, 52, 18,
};

static const Permutation p_U1 = {
  9 , 10, 11, 3 , 4 , 5 , 6 , 7 , 8 ,
  18, 19, 20, 12, 13, 14, 15, 16, 17,
  27, 28, 29, 21, 22, 23, 24, 25, 26,
  0 , 1 , 2 , 30, 31, 32, 33, 34, 35,
  42, 39, 36, 43, 40, 37, 44, 41, 38,
  45, 46, 47, 48, 49, 50, 51, 52, 53,
};

static const Permutation p_B1 = {
  0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
  9 , 10, 53, 12, 13, 52, 15, 16, 51,
  24, 21, 18, 25, 22, 19, 26, 23, 20,
  38, 28, 29, 37, 31, 32, 36, 34, 35,
  11, 14, 17, 39, 40, 41, 42, 43, 44,
  45, 46, 47, 48, 49, 50, 27, 30, 33,
};

static const Permutation p_r1 = {
  0 , 46, 47, 3 , 49, 50, 6 , 52, 53,
  15, 12, 9 , 16, 13, 10, 17, 14, 11,
  44, 43, 20, 41, 40, 23, 38, 37, 26,
  27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 1 , 2 , 39, 4 , 5 , 42, 7 , 8 ,
  45, 25, 24, 48, 22, 21, 51, 19, 18,
};

static const Permutation p_u1 = {
  9 , 10, 11, 12, 13, 14, 6 , 7 , 8 ,
  18, 19, 20, 21, 22, 23, 15, 16, 17,
  27, 28, 29, 30, 31, 32, 24, 25, 26,
  0 , 1 , 2 , 3 , 4 , 5 , 33, 34, 35,
  42, 39, 36, 43, 40, 37, 44, 41, 38,
  45, 46, 47, 48, 49, 50, 51, 52, 53,
};

static const Permutation p_b1 = {
  0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
  9 , 50, 53, 12, 49, 52, 15, 48, 51,
  24, 21, 18, 25, 22, 19, 26, 23, 20,
  38, 41, 29, 37, 40, 32, 36, 39, 35,
  11, 14, 17, 10, 13, 16, 42, 43, 44,
  45, 46, 47, 28, 31, 34, 27, 30, 33,
};

static Permutation p_R2, p_R3;
static Permutation p_U2, p_U3;
static Permutation p_B2, p_B3;
static Permutation p_r2, p_r3;
static Permutation p_u2, p_u3;
static Permutation p_b2, p_b3;

struct FourChars {uint8_t a, b, c, d;};
static FourChars center_variants[6][6];

typedef Permutation *PermutationPtr;
static PermutationPtr p_layer[8];

void PermValidate(const Permutation p) {
  uint8_t counters[kNumFacets];
  memset(counters, 0, sizeof(counters));
  for (int i = 0; i < kNumFacets; i++) {
    assert(p[i] < kNumFacets);
    counters[p[i]]++;
  }
  for (int i = 0; i < kNumFacets; i++)
    if (counters[i] != 1)
      printf("counters[%d] == %d\n", i, counters[i]);
  for (int i = 0; i < kNumFacets; i++)
    assert(counters[i] == 1);
}
// dst = p(src).
void PermApply(const Permutation src, const Permutation p, Permutation dst) {
  for (int i = 0; i < kNumFacets; i++)
    dst[i] = src[p[i]];
}

void PermPrint(const Permutation p, const char *name = 0) {
  if (name)
    printf("%s:\n", name);
  for (int i = 0; i < 6; i++) {
    for (int j = 0; j < 9; j++) {
      printf("%2d, ", p[i * 9 + j]);
    }
    // printf("\n");
  }
}

struct PermHash {
  uint64_t operator() (const Permutation p) const {
    uint64_t *x = (uint64_t*)p;
    return x[0] ^ x[1];
  }
};

struct PermEq {
  bool operator () (const Permutation p1, const Permutation p2) const {
    return memcmp(p1, p2, kNumFacets) == 0;
  }
};

bool PermIsZero(const Permutation p) {
  for (int i = 0; i < kNumFacets; i++)
    if (p[i] != i) return false;
  return true;
}

void InitCenterVariants() {
  center_variants[0][1] = {2,3,4,5};
  center_variants[0][3] = {2,1,5,4};
  center_variants[0][4] = {2,5,3,1};
  center_variants[0][5] = {2,4,1,3};
  center_variants[1][0] = {3,2,5,4};
  center_variants[1][2] = {3,0,4,5};
  center_variants[1][4] = {3,5,0,2};
  center_variants[1][5] = {3,4,2,0};
  center_variants[2][1] = {0,3,5,4};
  center_variants[2][3] = {0,1,4,5};
  center_variants[2][4] = {0,5,1,3};
  center_variants[2][5] = {0,4,3,1};
  center_variants[3][0] = {1,2,4,5};
  center_variants[3][2] = {1,0,5,4};
  center_variants[3][4] = {1,5,2,0};
  center_variants[3][5] = {1,4,0,2};
  center_variants[4][0] = {5,2,1,3};
  center_variants[4][1] = {5,3,2,0};
  center_variants[4][2] = {5,0,3,1};
  center_variants[4][3] = {5,1,0,2};
  center_variants[5][0] = {4,2,3,1};
  center_variants[5][1] = {4,3,0,2};
  center_variants[5][2] = {4,0,1,3};
  center_variants[5][3] = {4,1,2,0};
}

void PermInit() {
  PermApply(p_R1, p_R1, p_R2);
  PermApply(p_R2, p_R1, p_R3);
  PermApply(p_U1, p_U1, p_U2);
  PermApply(p_U2, p_U1, p_U3);
  PermApply(p_B1, p_B1, p_B2);
  PermApply(p_B2, p_B1, p_B3);

  PermApply(p_r1, p_r1, p_r2);
  PermApply(p_r2, p_r1, p_r3);
  PermApply(p_u1, p_u1, p_u2);
  PermApply(p_u2, p_u1, p_u3);
  PermApply(p_b1, p_b1, p_b2);
  PermApply(p_b2, p_b1, p_b3);
}

void PermGenMoves(Permutation p, Permutation moves[kNumMoves]) {
  PermApply(p, p_R1, moves[0]);
  PermApply(p, p_R2, moves[1]);
  PermApply(p, p_R3, moves[2]);

  PermApply(p, p_U1, moves[3]);
  PermApply(p, p_U2, moves[4]);
  PermApply(p, p_U3, moves[5]);

  PermApply(p, p_B1, moves[6]);
  PermApply(p, p_B2, moves[7]);
  PermApply(p, p_B3, moves[8]);

  PermApply(p, p_r1, moves[9]);
  PermApply(p, p_r2, moves[10]);
  PermApply(p, p_r3, moves[11]);

  PermApply(p, p_u1, moves[12]);
  PermApply(p, p_u2, moves[13]);
  PermApply(p, p_u3, moves[14]);

  PermApply(p, p_b1, moves[15]);
  PermApply(p, p_b2, moves[16]);
  PermApply(p, p_b3, moves[17]);
}

string PermToString(const Permutation p) {
  char buf[kNumFacets + 1];
  static const char p2c[] = 
    "abcdefghijklmnopqrstuvwxyz0ABCDEFGHIJKLMNOPQRSTUVWXYZ1";
  for (int i = 0; i < kNumFacets; i++) {
    buf[i] = p2c[p[i]];
  }
  buf[kNumFacets] = 0;
  return buf;
}

uint64_t PermSubsetHash(const Permutation p, uint64_t mask) {
  uint64_t res = 0;
  for (int i = 0; i < kNumFacets; i++) {
    if (mask & (1ULL << i))
      res = res * 6 + p[i] / 9;
  }
  return res;
}

struct Eq60 {
  bool operator () (uint64_t a, uint64_t b) const {
    return (a >> 4) == (b >> 4);
  }
};

struct Hash60 {
  uint64_t operator () (uint64_t a) const {
    return a >> 4;
  }
};

struct HashMap60vs4 : public std::unordered_set<uint64_t, Hash60, Eq60> {
  bool InsertWithDepth(uint64_t h, uint64_t depth) {
    assert(h < (1ULL << 60));
    assert(depth <= 15);
    std::pair<iterator, bool> r = insert((h << 4) | depth);
    if (r.second)
      return true;
    return false;
  }

  void DumpToFile(const char *filename) {
    FILE *f = fopen(filename, "w");
    assert(f);
    for (iterator it = begin(); it != end(); ++it) {
      uint64_t x = *it;
      fwrite(&x, 1, 8, f);
    }
    fclose(f);
  }
};

class Cube3x3 {
 public:
  // Red/Green/Yellow/Purple/Blue/Dark
  static const char color_codes[];
  static const char *html_color_codes[];
  void Clear() {
    memset(facet_, 0, kNumFacets);
  }
  int ColorCodeToColorNum(char color_code) {
    for (int i = 0; i < 6; i++)
      if (color_code == color_codes[i])
        return i;
    assert(0);
  }
  char ColorNumToColorCode(int color_num) {
    assert(color_num >= 0 && color_num < 6);
    return color_codes[color_num];
  }

  Cube3x3() {}
  Cube3x3(const char *str) {
    assert(strlen(str) == kNumFacets + 5);
    int idx = 0;
    for (int i = 0; i < 6; i++) {
      if (i)
        assert(str[idx++] == '-');
      for (int j = 0; j < 9; j++)
        facet_[i * 9 + j] = ColorCodeToColorNum(str[idx++]);
    }
    assert(idx == kNumFacets + 5);
  }

  Cube3x3(uint64_t hash1, uint64_t hash2) {
    SetFromHash1(hash1);
    SetFromEdgesHash(hash2);
  }

  Cube3x3(const Cube3x3 c, const Permutation p) {
    PermApply(c.facet_, p, this->facet_);
  }

  string ToString() {
    string res;
    for (int i = 0; i < 6; i++) {
      if (i)
        res += '-';
      for (int j = 0; j < 9; j++)
        res += ColorNumToColorCode(facet_[i * 9 + j]);
    }
    return res;
  }
  void GenMoves(Cube3x3 moves[kNumMoves]) const {
    GenOneMove(p_R1, moves, 0);
    GenOneMove(p_R2, moves, 1);
    GenOneMove(p_R3, moves, 2);

    GenOneMove(p_U1, moves, 3);
    GenOneMove(p_U2, moves, 4);
    GenOneMove(p_U3, moves, 5);

    GenOneMove(p_B1, moves, 6);
    GenOneMove(p_B2, moves, 7);
    GenOneMove(p_B3, moves, 8);

    GenOneMove(p_r1, moves, 9);
    GenOneMove(p_r2, moves, 10);
    GenOneMove(p_r3, moves, 11);

    GenOneMove(p_u1, moves, 12);
    GenOneMove(p_u2, moves, 13);
    GenOneMove(p_u3, moves, 14);

    GenOneMove(p_b1, moves, 15);
    GenOneMove(p_b2, moves, 16);
    GenOneMove(p_b3, moves, 17);
  }

  uint64_t CornersHash() const {
    assert(M(6) == 0);
    assert(M(35) == 3);
    assert(M(45) == 5);
    uint64_t res =
      M6(M(0*9+0), M6(M(0*9+2), /*0*9+6)*/   M6(M(0*9+8),
      M6(M(1*9+0), M6(M(1*9+2), M6(M(1*9+6), M6(M(1*9+8),
      M6(M(2*9+0), M6(M(2*9+2), M6(M(2*9+6), M6(M(2*9+8),
      M6(M(3*9+0), M6(M(3*9+2), M6(M(3*9+6), /*3*9+8*/
      M6(M(4*9+0), M6(M(4*9+2), M6(M(4*9+6), M6(M(4*9+8),
      /*5*9+0)*/   M6(M(5*9+2), M6(M(5*9+6), M(5*9+8)))))))))))))))))))));
    static const uint64_t six_to_21 = 21936950640377856ULL;
    assert(res < six_to_21);
    return res;
  }

  void SetFromCornersHash(uint64_t h) {
    facet_[6] = 0;
    facet_[35] = 3;
    facet_[45] = 5;
    facet_[0*9+0] = h % 6; h /= 6;
    facet_[0*9+2] = h % 6; h /= 6;
    facet_[0*9+8] = h % 6; h /= 6;
    facet_[1*9+0] = h % 6; h /= 6;
    facet_[1*9+2] = h % 6; h /= 6;
    facet_[1*9+6] = h % 6; h /= 6;
    facet_[1*9+8] = h % 6; h /= 6;
    facet_[2*9+0] = h % 6; h /= 6;
    facet_[2*9+2] = h % 6; h /= 6;
    facet_[2*9+6] = h % 6; h /= 6;
    facet_[2*9+8] = h % 6; h /= 6;
    facet_[3*9+0] = h % 6; h /= 6;
    facet_[3*9+2] = h % 6; h /= 6;
    facet_[3*9+6] = h % 6; h /= 6;
    facet_[4*9+0] = h % 6; h /= 6;
    facet_[4*9+2] = h % 6; h /= 6;
    facet_[4*9+6] = h % 6; h /= 6;
    facet_[4*9+8] = h % 6; h /= 6;
    facet_[5*9+2] = h % 6; h /= 6;
    facet_[5*9+6] = h % 6; h /= 6;
    facet_[5*9+8] = h % 6;
    assert(h < 6);
  }

  uint64_t SubsetHash(uint64_t mask) const {
    uint64_t res = 0;
    for (int i = 0; i < kNumFacets; i++) {
      if (mask & (1ULL << i))
        res = res * 6 + facet_[i];
    }
    return res;
  }

  void OneColorHash(uint64_t hash[6]) {
    for (int i = 0; i < 6; i++)
      hash[i] = 0;
    for (int i = 0; i < kNumFacets; i++)
      hash[facet_[i]] = (hash[facet_[i]] * kNumFacets) + i;
  }

  uint64_t OneColorHash(int c) {
    assert(c >= 0 && c < 6);
    uint64_t hash[6];
    OneColorHash(hash);
    return hash[c];
  }

  void SetFromOneColorHash(int color, uint64_t hash) {
    for (int i = 0; i < kNumFacets; i++)
      facet_[i] = (color + 1) % 6;
    for (int i = 0; i < 9; i++) {
      facet_[hash % 54] = color;
      hash /= 54;
    }
  }

  uint64_t EdgesHash() {
    uint64_t res = 0;
    for (int i = 0; i < kNumFacets; i += 9) {
      if (i) {
        res *= 6; res += M(i+1);
      }
      res *= 6; res += M(i+3);
      res *= 6; res += M(i+5);
      res *= 6; res += M(i+7);
    }
    static const uint64_t six_to_23 = 789730223053602816ULL;
    assert(res < six_to_23);
    return res;
  }

  void SetFromEdgesHash(uint64_t h) {
    int counters[6] = {0, 0, 0, 0, 0, 0};
    uint8_t t;
    for (int i = 5 * 9; i >= 0; i -= 9) {
      t = facet_[i+7] = h % 6; h /= 6; counters[t]++;
      t = facet_[i+5] = h % 6; h /= 6; counters[t]++;
      t = facet_[i+3] = h % 6; h /= 6; counters[t]++;
      if (i) {
        t = facet_[i+1] = h % 6; h /= 6; counters[t]++;
      }
    }
    for (int i = 0; i < 6; i++) {
      int c = counters[i];
      assert(c <= 4);
      if (c == 3)
        facet_[1] = i;
    }
  }
  void PrintCenter() {
    printf("[%zd][%zd] = {%zd,%zd,%zd,%zd};\n",
        M(4+0*9),
        M(4+1*9),
        M(4+2*9),
        M(4+3*9),
        M(4+4*9),
        M(4+5*9));
  }
  uint64_t CenterHash() {
    return M(4) + M(13) * 6;
  }
  void SetFromCenterHash(uint64_t h) {
    uint8_t i = facet_[4] = h % 6;
    uint8_t j = facet_[13] = h / 6;
    facet_[22] = center_variants[i][j].a;
    facet_[31] = center_variants[i][j].b;
    facet_[40] = center_variants[i][j].c;
    facet_[49] = center_variants[i][j].d;
  }

  uint64_t Hash1() {
    uint64_t res = (CornersHash() * 36) + CenterHash();
    assert(res < (1ULL << 60));
    return res;
  }

  void SetFromHash1(uint64_t h) {
    uint64_t corners = h / 36;
    uint64_t centers = h % 36;
    SetFromCornersHash(corners);
    SetFromCenterHash(centers);
  }

  bool operator == (const Cube3x3 c) const {
    return memcmp(facet_, c.facet_, kNumFacets) == 0;
  }
 private:
  inline uint64_t M(int i) const { return facet_[i]; }
  inline uint64_t M6(uint64_t a, uint64_t b) const { return a + 6 * b; }
  void GenOneMove(const Permutation p, Cube3x3 moves[kNumMoves],
                  int idx) const {
    PermApply(facet_, p, moves[idx].facet_);
  }
  Permutation facet_;
};


const char Cube3x3::color_codes[] = "RGYPBD";
const char *Cube3x3::html_color_codes[] = {
  "red", "green", "yellow", "purple", "blue", "gray"};

static const char *kInitialCube =
  "RRRRRRRRR-GGGGGGGGG-YYYYYYYYY-PPPPPPPPP-BBBBBBBBB-DDDDDDDDD";

static const Cube3x3 c0(kInitialCube);

void DFS_Print(Cube3x3 c, int depth) {
  printf("%d: %s\n", depth, c.ToString().c_str());
  if (!depth) return;
  Cube3x3 moves[kNumMoves];
  c.GenMoves(moves);
  for (int i = 0; i < kNumMoves; i++)
    DFS_Print(moves[i], depth - 1);
}

void BFS_CheckSanity(Cube3x3 c, int max_depth) {
  typedef std::unordered_map<string, int> Map;
  Map m;
  std::queue<Cube3x3> cur_q, next_q;
  cur_q.push(c);
  size_t prev_n = 0;
  for (int depth = 0; depth <= max_depth; depth++) {
    while (!cur_q.empty()) {
      Cube3x3 c1 = cur_q.front();
      // printf("check: %d: %s\n", depth, c1.ToString().c_str());
      cur_q.pop();
      string s = c1.ToString();
      Map::iterator it = m.find(s);
      if (it != m.end()) continue;
      m[s] = depth;
      // printf("%d: %s\n", depth, s.c_str());
      Cube3x3 moves[kNumMoves];
      c1.GenMoves(moves);
      if (depth == max_depth) continue;
      for (int i = 0; i < kNumMoves; i++)
        next_q.push(moves[i]);
    }
    size_t cur_n = m.size();
    // printf("[%d]: %zd\n", depth, cur_n - prev_n);
    assert(cur_n - prev_n == kNumPos[depth]);
    prev_n = cur_n;
    std::swap(cur_q, next_q);
  }
}

typedef std::unordered_set<string> PermSet;

string DbFileName(int depth) {
  char name[] = "0.db3x3";
  name[0] += depth;
  return name;
}

int GetNumberOfCores() {
  FILE *f = popen("grep processor /proc/cpuinfo | wc -l", "r");
  if (!f) return 1;
  int n = -1;
  int formatted = fscanf(f, "%d", &n);
  assert(formatted == 1);
  pclose(f);
  return n < 1 ? 1 : n;
}

struct BFS_PermWorkItem {
  Permutation *last_layer;
  const PermSet *s;
  size_t from, to;
  size_t *last_idx;
  FILE *file;
  pthread_mutex_t *mu;
};

void WriteToFileUnderLock(Permutation buff[], int size, BFS_PermWorkItem *wi) {
  // printf("WriteToFileUnderLock %d\n", size);
  if (!size) return;
  pthread_mutex_lock(wi->mu);
  *(wi->last_idx) += size;
  if (wi->file)
    fwrite(buff, size, kNumFacets, wi->file);
  pthread_mutex_unlock(wi->mu);
}

void *BFS_PermLatsLayerThread(void *arg) {
  BFS_PermWorkItem *wi = (BFS_PermWorkItem *)arg;
  assert(wi && wi->last_layer);
  static const int kBufSize = 1024;
  Permutation buff[kBufSize];
  int buf_pos = 0;
  for (size_t i = wi->from, to = wi->to; i < to; i++) {
    Permutation &p = wi->last_layer[i];
    Permutation moves[kNumMoves];
    PermGenMoves(p, moves);
    for (int m = 0; m < kNumMoves; m++) {
      Permutation &move = moves[m];
      if (wi->s->count(PermToString(move))) continue;
      Permutation back[kNumMoves];
      PermGenMoves(move, back);
      for (int b = 0; b < kNumMoves; b++) {
        if (!wi->s->count(PermToString(back[b]))) continue;
        if (PermEq()(p, back[b])) {
          if (buf_pos == kBufSize) {
            WriteToFileUnderLock(buff, buf_pos, wi);
            buf_pos = 0;
          }
          memcpy(buff[buf_pos++], move, kNumFacets);
        }
        break;
      }
    }
  }
  WriteToFileUnderLock(buff, buf_pos, wi);
  return NULL;
}

void BFS_PermLastLayer(int depth, Permutation *last_layer, const PermSet *s,
                       bool gen_files) {
  size_t last_idx = 0;
  int J = GetNumberOfCores();

  static const int kMaxThreads = 128;
  assert(J <= kMaxThreads);
  BFS_PermWorkItem wi[kMaxThreads];
  pthread_t thread[kMaxThreads];
  FILE *f = gen_files ? fopen(DbFileName(depth).c_str(), "w") : NULL;
  pthread_mutex_t mu;
  pthread_mutex_init(&mu, 0);

  size_t n = kNumPos[depth - 1];
  // printf("BFS_PermLastLayer: running %d threads\n", J);
  for (int t = 0; t < J; t++) {
    size_t from = t * (n / J);
    size_t to = t == J - 1 ? n : (t + 1) * (n / J);
    // printf("n=%zd t=%d; %zd %zd\n", n, t, from, to);
    wi[t] = BFS_PermWorkItem({last_layer, s, from, to, &last_idx, f, &mu});
    pthread_create(&thread[t], NULL, BFS_PermLatsLayerThread, &wi[t]);
    // BFS_PermLatsLayerThread(&wi[t]);
  }

  for (int t = 0; t < J; t++)
    pthread_join(thread[t], NULL);

  if (f)
    fclose(f);
  pthread_mutex_destroy(&mu);

  printf("%d: %zd\n", depth, last_idx);
  fflush(stdout);
  assert(last_idx == kNumPos[depth]);
}

void BFS_Perm(int max_depth, bool gen_files) {
  PermSet s;
  s.insert(PermToString(p_0));
  Permutation *layer[20] = {};
  layer[0] = new Permutation[kNumPos[0]];
  memcpy(layer[0][0], p_0, kNumFacets);
  for (int depth = 1; depth < max_depth; depth++) {
    Permutation *prev_layer = layer[depth - 1];
    assert(prev_layer);
    assert(layer[depth] == 0);
    Permutation *cur_layer = layer[depth] = new Permutation[kNumPos[depth]];
    size_t idx = 0;
    for (size_t i = 0, len = kNumPos[depth - 1]; i < len; i++) {
      Permutation &p = prev_layer[i];
      Permutation moves[kNumMoves];
      PermGenMoves(p, moves);
      for (int m = 0; m < kNumMoves; m++) {
        Permutation &move = moves[m];
        std::pair<PermSet::iterator, bool> res = s.insert(PermToString(move));
        if (!res.second) continue;
        assert(idx < kNumPos[depth]);
        memcpy(cur_layer[idx++], move, kNumFacets);
      }
    }
    assert(idx == kNumPos[depth]);
    printf("%d: %zd\n", depth, idx);
    if (gen_files) {
      FILE *f = fopen(DbFileName(depth).c_str(), "w");
      fwrite(cur_layer, idx, kNumFacets, f);
      fclose(f);
    }
    fflush(stdout);
  }

  Permutation *last_layer = layer[max_depth - 1];
  BFS_PermLastLayer(max_depth, last_layer, &s, gen_files);

  for (int depth = 0; depth <= max_depth; depth++)
    delete [] layer[depth];
}

void PrintPermCube(const Permutation p) {
  Cube3x3 c(kInitialCube);
  Cube3x3 c1(c, p);
  printf("%s\n", c1.ToString().c_str());
}

void CheckHashes(const Permutation p) {
  Cube3x3 c(kInitialCube);
  Cube3x3 c1(c, p);
  uint64_t corners_hash = c1.CornersHash();
  uint64_t edges_hash = c1.EdgesHash();
  uint64_t center_hash = c1.CenterHash();
  Cube3x3 c2;
  c2.SetFromCornersHash(corners_hash);
  c2.SetFromEdgesHash(edges_hash);
  c2.SetFromCenterHash(center_hash);
  assert(corners_hash == c2.CornersHash());
  assert(edges_hash == c2.EdgesHash());
  assert(center_hash == c2.CenterHash());
  if (!(c1 == c2)) {
    printf("%s: %lx\n", c1.ToString().c_str(), edges_hash);
    printf("%s: %lx\n", c2.ToString().c_str(), edges_hash);
  }
  assert(c1 == c2);
  Cube3x3 c3(c2.Hash1(), c2.EdgesHash());
  assert(c1 == c3);
  // printf("%s: %lx\n", c1.ToString().c_str(), corners_hash);
}

template<class Callback>
void IterateDb(int depth, Callback &callback) {
  FILE *f = fopen(DbFileName(depth).c_str(), "r");
  assert(f);
  static const int kBufSize = 1024;
  Permutation buff[kBufSize];
  int res;
  size_t total = 0;
  while ((res = fread(buff, kNumFacets, kBufSize, f)) > 0) {
    total += res;
    for (int i = 0; i < res; i++)
      callback(buff[i]);
  }
  assert(total == kNumPos[depth]);
  fclose(f);
}

void LoadLayers(int max_depth) {
  assert(max_depth <= 7);
  printf("Loading layers 1 .. %d\n", max_depth);
  p_layer[0] = new Permutation[1];
  memcpy(p_layer[0][0], p_0, kNumFacets);
  for (int d = 1; d <= max_depth; d++) {
    p_layer[d] = new Permutation[kNumPos[d]];
    FILE *f = fopen(DbFileName(d).c_str(), "r");
    assert(f);
    size_t res = fread((void*)p_layer[d], kNumFacets, kNumPos[d], f);
    assert(res == (size_t)kNumPos[d]);
    fclose(f);
  }
}

void BFS_EdgesAndCorners() {
  typedef std::unordered_set<uint64_t> Set;
  Cube3x3 c0(kInitialCube);
  Set se, sc;
  size_t prev_e = 0, prev_c = 0;
  int max1 = 6, max2 = 2;
  for (int d1 = 0; d1 <= max1; d1++) {
    const PermutationPtr layer = p_layer[d1];
    for (size_t i = 0, iend = kNumPos[d1]; i < iend; i++) {
      const Permutation &p = layer[i];
      Cube3x3 c(c0, p);
      // printf("  %s\n", c.ToString().c_str());
      se.insert(c.EdgesHash());
      sc.insert(c.CornersHash());
    }
    printf("%d: %zd %zd\n", d1, se.size() - prev_e, sc.size() - prev_c);
    fflush(stdout);
    prev_e = se.size();
    prev_c = sc.size();
  }
  const PermutationPtr layer1 = p_layer[max1];
  for (int d2 = 1; d2 <= max2; d2++) {
    const PermutationPtr layer2 = p_layer[d2];
    for (size_t i1 = 0, i1end = kNumPos[max1]; i1 < i1end; i1++) {
      Cube3x3 ct(c0, layer1[i1]);
      for (size_t i2 = 0, i2end = kNumPos[d2]; i2 < i2end; i2++) {
        Cube3x3 c(ct, layer2[i2]);
        se.insert(c.EdgesHash());
        // sc.insert(c.CornersHash());
      }
    }
    printf("%d: %zd %zd\n", d2 + max1, se.size() - prev_e, sc.size() - prev_c);
    fflush(stdout);
    prev_e = se.size();
    prev_c = sc.size();
  }
}

void EvaluateHash(int depth) {
  HashTable ht(28);
  Cube3x3 c0(kInitialCube);
  size_t prev_n = 0;
  printf("EvaluateHash %d\n", depth);
  fflush(stdout);
  for (int d = 0; d <= depth; d++) {
    const PermutationPtr layer = p_layer[d];
    for (size_t i = 0, iend = kNumPos[d]; i < iend; i++) {
      const Permutation &p = layer[i];
      Cube3x3 c(c0, p);
      // printf("  %s\n", c.ToString().c_str());
      uint64_t h = c.OneColorHash(0);
      ht.Insert(h, d);
      // ht.Insert(c.CornersHash(), d);
    }
    printf("%d: %zd; ht: %zd %zd\n", d, ht.n_inserts() - prev_n,
           ht.n_lookups(), ht.n_collisions());
    fflush(stdout);
    prev_n = ht.n_inserts();
  }
}

struct HashPermEval {
  std::unordered_map<uint64_t, int> ht;
  uint64_t mask;
  uint64_t max_size;
  int depth;
  bool stopped;
  void operator() (const Permutation p) {
    // Cube3x3 c(c0, p);
    // uint64_t h1 = c.SubsetHash(mask);
    uint64_t h = PermSubsetHash(p, mask);
    // assert(h == h1);
    if (ht.size() >= max_size) {
      stopped = true;
      return;
    }
    if (!ht.count(h))
      ht[h] = depth;
  }
};

string HeuristicFilename(int depth, uint64_t mask) {
  char buf[100];
  snprintf(buf, sizeof(buf), "heur-%d-%lx", depth, mask);
  return buf;
}

int EvaluateHashes(int depth, uint64_t mask, bool dump_to_file) {
  HashPermEval e;
  e.mask = mask;
  e.stopped = false;
  size_t prev = 1;
  for (int d = 1; d <= depth; d++) {
    e.depth = d;
    if (d <= 5)      e.max_size = 100000;
    else if (d == 6) e.max_size = 500000;
    else if (d == 7) e.max_size = 5000000;
    else if (d == 8) e.max_size = 20000000;
    IterateDb(d, e);
    if (e.stopped) {
      printf("stopped at depth %d: %zd elemets reached\n", d, e.max_size);
      return 1;
    }
    size_t cur_size = e.ht.size() - prev;
    size_t br_factor = e.ht.size() / prev;
    printf("%d: %zd %zd\n", d, cur_size, br_factor);
    fflush(stdout);
    if (cur_size == 0) return 1;
    if (d == 6) {
      if (cur_size <= 1000) return 1;
      if (br_factor <= 3) return 1;
    } else if (d == 7) {
      if (br_factor <= 2) return 1;
    }
    prev = e.ht.size();
  }
  printf("total %zdM\n", e.ht.size() / 1000000);
  if (dump_to_file) {
    FILE *f = fopen(HeuristicFilename(depth, mask).c_str(), "w");
    assert(f);
    for (std::unordered_map<uint64_t, int>::iterator it = e.ht.begin();
         it != e.ht.end(); ++it) {
      uint64_t x = it->first;
      assert(x < (1ULL << 60));
      int d = it->second;
      x = (x << 4) | d;
      fwrite(&x, 1, 8, f);
    }
    fclose(f);
  }
  return 0;
}

uint64_t RandomMask(int len) {
  Permutation p;
  memcpy(p, p_0, sizeof(p));
  std::random_shuffle(p, p + kNumFacets);
  uint64_t mask = 0;
  for (int i = 0; i < len; i++)
    mask |= 1ULL << p[i];
  return mask;
}

int EvaluateRandomSubset(int depth) {
  while (true) {
    int len = (rand() % 19) + 5;
    uint64_t mask = RandomMask(len);
    printf("Subset %lx len=%d\n", mask, len);
    if (EvaluateHashes(depth, mask, false) == 0)
      break;
  }
  return 0;
}

int PrintRandomCube(int depth) {
  Cube3x3 c(c0);
  for (int i = 0; i < depth; i++) {
    Cube3x3 moves[kNumMoves];
    c.GenMoves(moves);
    c = moves[rand() % kNumMoves];
  }
  printf("%s\n", c.ToString().c_str());
  return 0;
}

struct Heuristic {
  uint64_t mask;
  int depth;
  HashMap60vs4 ht;
  bool HasCubeAtDepth(Cube3x3 &c, int depth) {
    uint64_t hash = c.SubsetHash(mask);
    HashMap60vs4::iterator it = ht.find(hash << 4);
    if (it == ht.end()) return false;
    if ((*it & 15) > depth) return false;
    return true;
  }
};

void LoadHeuristic(Heuristic &heur, int depth, uint64_t mask) {
  string filename = HeuristicFilename(depth, mask);
  printf("loading %s: ", filename.c_str());
  FILE *f = fopen(filename.c_str(), "r");
  assert(f);
  uint64_t x;
  int counters[20] = {};
  int total = 0;
  while (fread(&x, 8, 1, f) > 0) {
    int depth = x & 15;
    counters[depth]++;
    x >>= 4;
    bool inserted = heur.ht.InsertWithDepth(x, depth);
    assert(inserted);
    total++;
  }
  heur.depth = depth;
  heur.mask = mask;

  fclose(f);

  for (int i = 1; i <= depth; i++) {
    printf("%d ", counters[i]);
  }
  printf("; %d total\n", total);
  fflush(stdout);
}

Heuristic heur[100];
int n_heur = 0;

int DFS(Cube3x3 &c, int depth, int moves[]) {
  if (depth == 0) {
    if (c == c0) {
      return 1;
    }
    return 0;
  }
  for (int i = 0; i < n_heur; i++) {
    Heuristic &he = heur[i];
    if (depth <= he.depth && !he.HasCubeAtDepth(c, depth))
      return 0;
  }
  Cube3x3 cmoves[kNumMoves];
  c.GenMoves(cmoves);
  for (int m = 0; m < kNumMoves; m++) {
    moves[depth] = m;
    if (DFS(cmoves[m], depth - 1, moves))
      return 1;
  }
  return 0;
}

void PrintMoveSequence(const Cube3x3 &c, int moves[], int depth) {
  Cube3x3 c1(c);
  for (int d = depth; d > 0; d--) {
    printf(" [%2d] %s %d\n", d, c1.ToString().c_str(), moves[d]);
    Cube3x3 cmoves[kNumMoves];
    c1.GenMoves(cmoves);
    c1 = cmoves[moves[d]];
  }
  printf(" [ 0] %s\n", c1.ToString().c_str());
}

int IDAstar(Cube3x3 &c, int max_depth) {
  LoadHeuristic(heur[n_heur++], 8, 0x8B45A2D168B45);
  LoadHeuristic(heur[n_heur++], 8, 0x18900001148005);
  LoadHeuristic(heur[n_heur++], 8, 0x29841e08000005);
  LoadHeuristic(heur[n_heur++], 8, 0x41209048902);
  LoadHeuristic(heur[n_heur++], 8, 0x8004005108005);
  LoadHeuristic(heur[n_heur++], 8, 0x8b54208020004);
  LoadHeuristic(heur[n_heur++], 8, 0x28940000028881);
  LoadHeuristic(heur[n_heur++], 8, 0x800d000028a05);
  LoadHeuristic(heur[n_heur++], 8, 0x105004128047 );
  LoadHeuristic(heur[n_heur++], 8, 0x20005128028204);
  clock_t t = clock();
  int moves[21];
  for (int d = 0; d <= max_depth; d++) {
    int found = DFS(c, d, moves);
    clock_t elapsed = clock() - t;
    if (elapsed * 10 / CLOCKS_PER_SEC)
      printf("%d: %zd\n", d,  elapsed / CLOCKS_PER_SEC);
    if (found) {
      PrintMoveSequence(c, moves, d);
      return d;
    }
    t = clock();
  }
  return -1;
}

int SolveCube(const char *str) {
  Cube3x3 c(str);
  printf("solving %s\n", c.ToString().c_str());
  int res = IDAstar(c, 20);
  if (res >= 0)
    printf("found at depth %d\n", res);
  return 0;
}

void ConstructInitialHashTable(int depth) {
  HashTable ht(28);
  Cube3x3 c0(kInitialCube);
  size_t prev_n = 0;
  printf("ConstructInitialHashTable %d\n", depth);
  fflush(stdout);
  for (int d = 0; d <= depth; d++) {
    const PermutationPtr layer = p_layer[d];
    for (size_t i = 0, iend = kNumPos[d]; i < iend; i++) {
      const Permutation &p = layer[i];
      Cube3x3 c(c0, p);
      // printf("  %s\n", c.ToString().c_str());
      uint64_t h = c.EdgesHash();
      ht.Insert(h, d);
      // ht.Insert(c.CornersHash(), d);
    }
    printf("%d: %zd; ht: %zd %zd\n", d, ht.n_inserts() - prev_n,
           ht.n_lookups(), ht.n_collisions());
    fflush(stdout);
    prev_n = ht.n_inserts();
  }
}

void BFS_OneColor(int color, uint64_t max_depth) {
  HashTable ht(29);
  Cube3x3 c0(kInitialCube);
  ht.Insert(c0.OneColorHash(color), 0);
  clock_t t = clock();
  size_t prev = 0;
  for (uint64_t depth = 1; depth <= max_depth; depth++) {
    for (size_t i = 0, n = ht.size(); i < n; i++) {
      uint64_t h = ht.raw(i);
      if (!h)
        continue;
      // printf("raw: %zd\n", i);
      uint64_t elem_depth = h >> 60;
      uint64_t elem_hash = (h << 4) >> 4;
      if (elem_depth != depth - 1)
        continue;
      Cube3x3 c, moves[kNumMoves];
      c.SetFromOneColorHash(color, elem_hash);
      c.GenMoves(moves);
      for (int m = 0; m < kNumMoves; m++)
        ht.Insert(moves[m].OneColorHash(color), depth);
    }
    printf("depth: %02ld: % 10zd; % 10zd lookups; % 9zd collisions; time %zd\n",
           depth,
           ht.n_inserts() - prev,
           ht.n_lookups(),
           ht.n_collisions(),
           (clock() - t) / CLOCKS_PER_SEC);
    fflush(stdout);
    t = clock();
    prev = ht.n_inserts();
  }
}

HashMap60vs4 scan_ht;
uint64_t scan_mask;
bool scan_stopped;

size_t DFScan(const Cube3x3 &c, int search_depth, int cur_depth, int moves[]) {
  if (cur_depth == 0) {
    size_t s = scan_ht.size();
    bool stop = false;
    if (search_depth <= 5 && s >= 100000) stop = true;
    if (search_depth == 6 && s >= 500000) stop = true;
    if (search_depth == 7 && s >= 5000000) stop = true;
    if (search_depth == 9 && s >= 20000000) stop = true;
    if (stop) {
      scan_stopped = true;
      return 0;
    }

    scan_ht.InsertWithDepth(c.SubsetHash(scan_mask), search_depth);
    return 1;
  }

  size_t res = 0;
  Cube3x3 cmoves[kNumMoves];
  c.GenMoves(cmoves);
  int prev_move = moves[cur_depth + 1];
  for (int m = 0; m < kNumMoves; m++) {
    if (prev_move >= 0 && prev_move / 3 == m / 3) continue;
    moves[cur_depth] = m;
    res += DFScan(cmoves[m], search_depth, cur_depth - 1, moves);
    if (scan_stopped)
      break;
  }
  return res;
}

int IDScan(int max_depth, uint64_t mask) {
  scan_mask = mask;
  scan_ht.clear();
  scan_stopped = false;
  int moves[21];
  size_t prev = 0;
  clock_t t = clock();
  for (int d = 0; d <= max_depth; d++) {
    moves[d + 1] = -1;
    size_t scanned = DFScan(c0, d, d, moves);
    if (scan_stopped) {
      printf("scan stoped at depth %d\n", d);
      return 1;
    }
    size_t cur_size = scan_ht.size() - prev;
    size_t br_factor = scan_ht.size() / (prev ? prev : (prev + 1));
    if (d >= 5) {
      printf("%d: %10zd %2zd; scanned %12zd; t %6zd\n",
             d,
             cur_size,
             br_factor,
             scanned,
             (clock() - t) / CLOCKS_PER_SEC);
      fflush(stdout);
    }

    if (cur_size == 0) return 1;
    if (d == 6) {
      if (cur_size <= 1000) return 1;
      if (br_factor <= 3) return 1;
    } else if (d == 7) {
      if (br_factor <= 2) return 1;
    } else if (d == 8) {
      // if (br_factor <= 1) return 1;
    }

    if (d >= 8) {
      string filename = HeuristicFilename(d, mask);
      printf("dumping to %s .. ", filename.c_str());
      scan_ht.DumpToFile(filename.c_str());
      printf("done\n");
    }

    prev = scan_ht.size();
  }
  return 0;
}

int IDScanLoop(int max_depth) {
  while (true) {
    int len = (rand() % 19) + 5;
    uint64_t mask = RandomMask(len);
    printf("Subset %lx len=%d\n", mask, len);
    if (!IDScan(max_depth, mask))
      return 0;
  }
}

void test() {
  TestHashTable();
  PermInit();
  InitCenterVariants();
  Permutation p_t;
  assert(PermIsZero(p_0));

  PermValidate(p_R1);
  PermValidate(p_R2);
  PermValidate(p_R3);
  PermApply(p_R3, p_R1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_R1, p_t);
  assert(memcmp(p_R1, p_t, kNumFacets) == 0);

  PermValidate(p_U1);
  PermValidate(p_U2);
  PermValidate(p_U3);
  PermApply(p_U3, p_U1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_U1, p_t);
  assert(memcmp(p_U1, p_t, kNumFacets) == 0);

  PermValidate(p_B1);
  PermValidate(p_B2);
  PermValidate(p_B3);
  PermApply(p_B3, p_B1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_B1, p_t);
  assert(memcmp(p_B1, p_t, kNumFacets) == 0);

  PermValidate(p_r1);
  PermValidate(p_r2);
  PermValidate(p_r3);
  PermApply(p_r3, p_r1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_r1, p_t);
  assert(memcmp(p_r1, p_t, kNumFacets) == 0);

  PermValidate(p_u1);
  PermValidate(p_u2);
  PermValidate(p_u3);
  PermApply(p_u3, p_u1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_u1, p_t);
  assert(memcmp(p_u1, p_t, kNumFacets) == 0);

  PermValidate(p_b1);
  PermValidate(p_b2);
  PermValidate(p_b3);
  PermApply(p_b3, p_b1, p_t);
  assert(PermIsZero(p_t));
  PermApply(p_0, p_b1, p_t);
  assert(memcmp(p_b1, p_t, kNumFacets) == 0);


  Cube3x3 c(kInitialCube);
  assert(c.ToString() == kInitialCube);

//  DFS_Print(c, 2);
  BFS_CheckSanity(c, 4);
}

int main(int argc, char **argv) {
  srand(time(0) + getpid());
  PermInit();
  InitCenterVariants();
  test();
  if (argc >= 2 && string(argv[1]) == "gendb8") {
    BFS_Perm(8, true);
    return 0;
  }
  if (argc >= 2 && string(argv[1]) == "gendb7") {
    BFS_Perm(7, true);
    return 0;
  }
  if (argc >= 2 && string(argv[1]) == "gendb6") {
    BFS_Perm(6, true);
    return 0;
  }
  // int depth = 5;
  // LoadLayers(depth);
  // EvaluateHash(depth);
  // IterateDb(1, PrintPermCube);
  // printf("checking\n");
  for (int d = 1; d <= 5; d++) {
    IterateDb(d, CheckHashes);
  }

//  if (argc == 4 && string(argv[1]) == "eval_subset")
//    return EvaluateHashes(8, atoi(argv[2]), atoi(argv[3]));

  if (argc == 2 && string(argv[1]) == "eval_rand")
    return EvaluateRandomSubset(7);
  if (argc == 3 && string(argv[1]) == "eval")
    return EvaluateHashes(8, strtoul(argv[2], 0, 16), false);

  if (argc == 3 && string(argv[1]) == "gen_heuristic")
    return EvaluateHashes(8, strtoul(argv[2], 0, 16), true);


  if (argc == 3 && string(argv[1]) == "random_cube")
    return PrintRandomCube(atoi(argv[2]));

  if (argc == 3 && string(argv[1]) == "solve")
    return SolveCube(argv[2]);

  if (argc == 2 && string(argv[1]) == "scan")
    return IDScanLoop(10);

  if (argc == 2 && string(argv[1]) == "scan_bench")
    return IDScan(7, 0x8B45A2D168B45);

  for (int d = 1; d <= 3; d++) {
    // printf("---- %d\n", d);
    // BFS_Perm(d, false);
  }
  // ConstructInitialHashTable(depth);
  // BFS_EdgesAndCorners();
  for (int c = 0; c < 6; c++) {
    // BFS_OneColor(c, 11);
  }
}
